#include <iostream>

// TIP 要<b>Run</b>代码，请按 <shortcut actionId="Run"/> 或点击装订区域中的 <icon src="AllIcons.Actions.Execute"/> 图标。
using namespace std;

int func1() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    int X, Y;
    cin >> X >> Y;
    --X; --Y; // 转换成0-based

    vector<vector<int>> h(N, vector<int>(M));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> h[i][j];
        }
    }

    int h0 = h[X][Y]; // 起点高度
    vector<vector<bool>> vis(N, vector<bool>(M, false));
    queue<pair<int,int>> q;

    q.push({X, Y});
    vis[X][Y] = true;
    int ans = 0;

    int dx[4] = {1,-1,0,0};
    int dy[4] = {0,0,1,-1};

    while (!q.empty()) {
        auto [x,y] = q.front(); q.pop();
        ans++;
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx>=0 && nx<N && ny>=0 && ny<M && !vis[nx][ny]) {
                if (h[nx][ny] >= h0) {
                    vis[nx][ny] = true;
                    q.push({nx,ny});
                }
            }
        }
    }

    cout << ans << "\n";
    return 0;
}


struct Func {
    string name;
    string args; // 参数类型字符串, 例如 "ssi"
};

long long readInt(const string &s, int pos) {
    long long val = 0;
    for (int i = 0; i < 4; i++) {
        val = (val << 8) | stoll(s.substr(pos + i*2, 2), nullptr, 16);
    }
    if (val & (1LL << 31)) val -= (1LL << 32);
    return val;
}

string readString(const string &s, int &pos) {
    long long len = readInt(s, pos);
    pos += 8;
    string res;
    for (int i = 0; i < len; i++) {
        res += s.substr(pos, 2);
        pos += 2;
    }
    return "\"" + res + "\"";
}

int func2() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    unordered_map<int, Func> funcs;
    for (int i = 0; i < n; i++) {
        int id; string name, args;
        cin >> id >> name >> args;
        funcs[id] = {name, args};
    }

    string hexstr;
    cin >> hexstr;

    int pos = 0;
    while (pos + 2 <= (int)hexstr.size()) {  // 确保还能读到下一个rpcId
        int rpcId = stoi(hexstr.substr(pos, 2), nullptr, 16);
        pos += 2;

        auto f = funcs[rpcId];
        vector<string> params;

        for (char c : f.args) {
            if (c == 'i') {
                long long val = readInt(hexstr, pos);
                pos += 8;
                params.push_back(to_string(val));
            } else if (c == 's') {
                string strVal = readString(hexstr, pos);
                params.push_back(strVal);
            }
        }

        cout << f.name << "(";
        for (int i = 0; i < (int)params.size(); i++) {
            if (i) cout << ",";
            cout << params[i];
        }
        cout << ")\n";
    }

    return 0;
}


#include <bits/stdc++.h>
using namespace std;

/*
题意转化：
- 设 L = Hp - UpperHp，R = Hp - LowerHp。
- 求最小攻击次数，使得总伤害 S ∈ [L, R)。
- 每次可选任意 D_i（可重复），N<=10，Hp<=1000。

做法：
- 完全背包（最少硬币数）：dp[s] = 凑出总伤害 s 的最少次数，初始化 dp[0]=0，其它为 INF。
- 转移：dp[s] = min(dp[s], dp[s - d] + 1)  (对每个 d ∈ D，且 s>=d)。
- 答案：min_{s ∈ [L, R)} dp[s]；若均为 INF，则 -1。
*/

int func3() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int M;                   // 组数
    if (!(cin >> M)) return 0;
    while (M--) {
        int Hp, LowerHp, UpperHp, N;
        cin >> Hp >> LowerHp >> UpperHp >> N;
        vector<int> D(N);
        for (int i = 0; i < N; ++i) cin >> D[i];

        int L = Hp - UpperHp;   // 包含
        int R = Hp - LowerHp;   // 不包含

        // 若区间非法或无需攻击（例如 L<=0），把下界提到 0
        if (R <= 0) {           // UpperHp >= Hp，第一次就进虚弱？
            cout << 0 << "\n";
            continue;
        }
        L = max(0, L);          // 允许总伤害从 0 开始考察

        const int INF = 1e9;
        vector<int> dp(R, INF);
        dp[0] = 0;
        for (int s = 1; s < R; ++s) {
            for (int d : D) {
                if (s - d >= 0 && dp[s - d] != INF) {
                    dp[s] = min(dp[s], dp[s - d] + 1);
                }
            }
        }

        int ans = INF;
        for (int s = L; s < R; ++s) ans = min(ans, dp[s]);

        cout << (ans == INF ? -1 : ans) << "\n";
    }
    return 0;
}



int func4() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<pair<int,long long>> skills(n);
    int max_end = 0;
    for (int i = 0; i < n; i++) {
        int a; long long b;
        cin >> a >> b;
        skills[i] = {a, b};
        max_end = max(max_end, a + m);
    }

    // 差分数组
    vector<long long> diff(max_end + 2, 0);

    for (auto &sk : skills) {
        int a = sk.first;
        long long b = sk.second;
        diff[a] += b;
        diff[a + m] -= b;  // 右端开区间
    }

    long long cur = 0, ans = 0;
    for (int t = 0; t <= max_end; t++) {
        cur += diff[t];
        ans = max(ans, cur);
    }

    cout << ans << "\n";
    return 0;
}